
from math import sqrt

def centerRectangles(rectangles, cx, cy):
    "modify rectangles in place to put center at cx, cy"
    if not rectangles:
        return rectangles # nothing to center
    geometries = [r.geometry() for r in rectangles]
    xmins = [ g[0] for g in geometries ]
    ymins = [ g[1] for g in geometries ]
    xmaxs = [ g[2] for g in geometries ]
    ymaxs = [ g[3] for g in geometries ]
    xmin = min(xmins)
    ymin = min(ymins)
    xmax = max(xmaxs)
    ymax = max(ymaxs)
    xmid = (xmin+xmax)/2.0
    ymid = (ymin+ymax)/2.0
    dx = cx-xmid
    dy = cy-ymid
    for r in rectangles:
        r.xmin += dx
        r.ymin += dy
    return rectangles

def vectorCosine(cx, cy, ax, ay, bx, by):
    x0 = ax-cx
    y0 = ay-cy
    x1 = bx-cx
    y1 = by-cy
    d0 = sqrt( x0*x0 + y0*y0 )
    d1 = sqrt( x1*x1 + y1*y1 )
    if d0<0.01 or d1<0.01: return 1.0 # lengths too small to compare
    ux0 = x0/d0
    uy0 = y0/d0
    ux1 = x1/d1
    uy1 = y1/d1
    return ux0*ux1 + uy0*uy1

def dist(x0,y0,x1,y1):
    dx = x0-x1
    dy = y0-y1
    return sqrt( dx*dx + dy*dy )

def overlapping(min1, max1, min2, max2):
    if (min1<=min2) and (min2<=max1):
        return True
    if (min2<=min1) and (min1<=max2):
        return True
    if (min1<=max2) and (max2<=max1):
        return True
    if (min2<=max1) and (max1<=max2):
        return True
    return False

def minAbsDifference(a1, a2, b1, b2):
    if a2<=b1:
        return b1-a2
    else:
        assert b2<=a1, "bad intervals? "+repr((a1, a2, b1, b2))
        return a1-b2

def layoutRectangles(idToRectangle, adjacentPairs,
                     initOffset=200, reduction=0.7, borderSize=10, repulsionFactor=200, attractionFactor=1, offsetLimit=10,
                     debug=False, fixedIdToRectangle={}, radius=None):
    if not idToRectangle:
        # nothing to adjust
        return idToRectangle
    if debug:
        htmlfn = "/tmp/layout.html"
        htmlOut = open(htmlfn, "w")
    idToRectangle = idToRectangle.copy()
    idToNeighborMap = {}
    allRectangles = fixedIdToRectangle.copy()
    allRectangles.update(idToRectangle)
    centerRectangles(allRectangles.values(), 0,0)
    for (a,b) in adjacentPairs:
        for (x,y) in ((a,b), (b,a)):
            if x in allRectangles and y in allRectangles:
                D = idToNeighborMap.get(x, {})
                D[y] = 1
                idToNeighborMap[x] = D
    idToNeighborList = {}
    for a in idToNeighborMap:
        D = idToNeighborMap[a]
        L = D.keys()
        L.sort()
        idToNeighborList[a] = L
    allids = allRectangles.keys()
    allids.sort()
    ids = []
    for id in idToRectangle:
        if id not in fixedIdToRectangle:
            ids.append(id)
    ids.sort()
    if debug:
                pngfn = "/tmp/layout_start.png" 
                print "dumping", pngfn
                htmlOut.write("<br> <h1> %s </h1> \n" % pngfn)
                htmlOut.write('<br> <img src="%s"> \n' % pngfn)
                from skimpyGimpy import canvas
                c = canvas.Canvas()
                for R in allRectangles.values():
                    c.setColor(*R.info)
                    c.addRect(R.xmin, R.ymin, R.height, R.width)
                c.setColor(0,0,255)
                c.setCap(1)
                c.setWidth(1)
                for (a, b) in adjacentPairs:
                    R1 = allRectangles.get(a)
                    R2 = allRectangles.get(b)
                    if R1 and R2:
                        print "connect", (R1, R2)
                        triangle = [ (R1.xmin, R1.ymin), (R2.xmin, R2.ymin) ]
                        c.addLines( triangle, closed=False )
                c.setColor(255,0,0)
                c.addLines( [ (-20,-20), (20, 20), (20,-20), (-20,20) ] )
                c.dumpToPNG(pngfn)
    offset = initOffset
    warmups = []
    cooldowns = []
    while offset>offsetLimit:
        warmups.append(offset)
        offset = int(offset*reduction)
        cooldowns.append(offset)
        offset = int(offset*reduction)
    warmups.reverse()
    #while offset>offsetLimit:
    for offset in warmups+cooldowns:
        #pr
        #pr "offset", offset
        #newidToRectangle = {}
        for id in ids:
            neighborIds = idToNeighborList.get(id, ())
            R = idToRectangle[id]
            # these lists change for each iteration
            Rectangles = [ allRectangles[i] for i in allids ]
            Neighbors = [ allRectangles[i] for i in neighborIds ]
            #pr "for", (id,R)
            #pr "    ", neighborIds
            newR = R.shift(offset, Rectangles, Neighbors,
                           bordersize=borderSize, repulsionFactor=repulsionFactor, attractionFactor=attractionFactor, radius=radius)
            #pr "    new=", newR
            idToRectangle[id] = newR
            allRectangles[id] = newR
            if debug:
                pngfn = "/tmp/layout%s_%s.png" % (offset, id)
                #pr "dumping", pngfn
                htmlOut.write("<br> <h1> %s </h1> \n" % pngfn)
                htmlOut.write('<br> <img src="%s"> \n' % pngfn)
                from skimpyGimpy import canvas
                c = canvas.Canvas()
                for R in allRectangles.values():
                    c.setColor(*R.info)
                    c.addRect(R.xmin, R.ymin, R.height, R.width)
                c.setColor(0,0,255)
                c.setCap(1)
                c.setWidth(1)
                for (a, b) in adjacentPairs:
                    R1 = allRectangles.get(a)
                    R2 = allRectangles.get(b)
                    if R1 and R2:
                        #pr "connect", (R1, R2)
                        triangle = [ (R1.xmin, R1.ymin), (R2.xmin, R2.ymin) ]
                        c.addLines( triangle, closed=False )
                c.setColor(255,0,0)
                c.addLines( [ (-20,-20), (20, 20), (20,-20), (-20,20) ] )
                c.dumpToPNG(pngfn)
        #offset = int(offset*reduction)
    if debug:
        htmlOut.close()
        #pr "wrote debug html", htmlfn
    return idToRectangle

DELTAS = ( (0,0),
           (1,0), (-1,0), (0,1), (-1,0),
           (0.7, 0.7),(-0.7, 0.7),(0.7, -0.7),(-0.7, -0.7),
           (0.4,0.4), (-0.4,0.4), (0.4,-0.4), (-0.4,-0.4),
           #(2,1), (-1,2), (-2,-1), (1,-2),
           )

class Rect:
    def __init__(self, xmin, ymin, height, width, info=None):
        self.xmin = xmin
        self.ymin = ymin
        self.height = height
        self.width = width
        self.info = info
    def shift(self, offset, otherRectangles, connectedRectangles, repulsionFactor=1.0, attractionFactor=1.0, bordersize=0.0, radius=None):
        bestpenalty = None
        replacementRectangle = None
        for (dx, dy) in DELTAS:
            testRectangle = self.offset( int(dx*offset), int(dy*offset) )
            p = self.penalty(testRectangle, otherRectangles, connectedRectangles, repulsionFactor, attractionFactor, bordersize, radius=radius)
            #pr "test", testRectangle, p
            if bestpenalty is None or p<=bestpenalty:
                replacementRectangle = testRectangle
                bestpenalty = p
                #pr "replacement", replacementRectangle, bestpenalty
        #pr "replace", self, replacementRectangle, bestpenalty
        #pr
        return replacementRectangle
    def penalty(self, testRectangle, otherRectangles, connectedRectangles, repulsionFactor=1.0, attractionFactor=1.0, bordersize=0.0, radius=None):
        #pr "computing penalty for", testRectangle, "with bordersize", bordersize, "connected to", connectedRectangles
        # initial penalty is distance from initial position and origin scaled by attractionfactor
        #result = 0
        (xmin, ymin, xmax, ymax, h, w, cx, cy) = testRectangle.geometry()
        if radius:
            if abs(xmin)>radius or abs(xmax)>radius or abs(ymin)>radius or abs(ymax)>radius:
                # big penalty
                return 1e16
        result = (dist(self.xmin,self.ymin, xmin, ymin)+dist(xmin,ymin,0,0))*attractionFactor
        # this could be optimized, maybe
        # find coincidence of vectors leading from testrectangle
        nc = len(connectedRectangles)
        if nc>1:
            coincidence = 0
            for i in xrange(nc-1):
                ri = connectedRectangles[i]
                for j in xrange(i,nc):
                    rj = connectedRectangles[j]
                    cosine = vectorCosine(xmin, ymin, ri.xmin, ri.ymin, rj.xmin, rj.ymin)
                    coincidence += 1+cosine
            #pr "coincidence", coincidence, "with", connectedRectangles
            result += repulsionFactor*coincidence
        #pr "   origin penalty", result
        for r in otherRectangles:
            if r is not self:
                # add weak crowding penalty
                #d = r.distance(testRectangle)
                #c = int(10000000.0/(10000.0+d))
                #if c:
                #    result += c
                #    #pr "   ", r, "crowds", testRectangle, c, result
                test = r.overlap(testRectangle, bordersize)
                if test>0:
                    #pr "   ", r, "repulses", testRectangle, test, "+", result
                    result += test*repulsionFactor
                else:
                    #pr "   no overlap", r, testRectangle
                    pass
        for r in connectedRectangles:
            if r is not self:
                test = r.distance(testRectangle)
                if test>0:
                    #pr "    ", r, "attracts", testRectangle, test, "+", result
                    result += test*test*attractionFactor
                else:
                    #pr "    no distance", r, testRectangle
                    pass
        #pr "  final penalty=", result
        return result
    def __repr__(self):
        return "Rect"+repr((self.xmin, self.ymin, self.height, self.width, self.info))
    def offset(self, dx, dy):
        return Rect(self.xmin+dx, self.ymin+dy, self.height, self.width, self.info)
    def intersection(self, other, bordersize=0):
        (myminx, myminy, mymaxx, mymaxy, myh, myw, mycx, mycy) = self.geometry(bordersize)
        (otherminx, otherminy, othermaxx, othermaxy, otherh, otherw, othercx, othercy) = other.geometry(bordersize)
        minx = max(myminx, otherminx)
        miny = max(myminy, otherminy)
        maxx = min(mymaxx, othermaxx)
        maxy = min(mymaxy, othermaxy)
        height = maxx-minx
        width = maxy-miny
        if height>0 and width>0:
            return Rect(minx, miny, height, width)
        else:
            return None
    def distance(self, other, bordersize=0):
        (myminx, myminy, mymaxx, mymaxy, myh, myw, mycx, mycy) = self.geometry(bordersize)
        (otherminx, otherminy, othermaxx, othermaxy, otherh, otherw, othercx, othercy) = other.geometry(bordersize)
        # shortcut: use center distance if it is larger than 3 x max extent
        maxextent = max(myh, myw, otherh, otherw)
        cdist = dist(mycx, mycy, othercx, othercy)
        if cdist>3*maxextent:
            return cdist
        xoverlap = overlapping(myminx, mymaxx, otherminx, othermaxx)
        yoverlap = overlapping(myminy, mymaxy, otherminy, othermaxy)
        if xoverlap:
            if yoverlap:
                return 0
            else:
                return minAbsDifference(myminy, mymaxy, otherminy, othermaxy)
        elif yoverlap:
            return minAbsDifference(myminx, mymaxx, otherminx, othermaxx)
        else:
            distance = dist(myminx, myminy, othermaxx, othermaxy)
            distance = min(distance, dist(mymaxx, myminy, otherminx, othermaxy))
            distance = min(distance, dist(myminx, mymaxy, othermaxx, otherminy))
            distance = min(distance, dist(mymaxx, mymaxy, otherminx, otherminy))
            return distance
    def overlap(self, other, bordersize=0):
        #pr "computing overlap", self, other, bordersize
        intersect = self.intersection(other, bordersize)
        #pr "intersect is", intersect
        if intersect is None:
            return 0
        sarea = self.area()
        oarea = other.area()
        minarea = min(sarea, oarea)
        intarea = intersect.area()
        if intarea>=minarea:
            ratio = 1
        else:
            ratio = float(intarea)/minarea
        return ratio * (sarea+oarea)
    def area(self):
        return self.height * self.width
    def geometry(self, bordersize=0):
        h = self.height
        w = self.width
        minx = self.xmin
        miny = self.ymin
        maxx = minx + h
        maxy = miny + w
        return (minx-bordersize, miny-bordersize, maxx+bordersize, maxy+bordersize, h, w, minx+h/2.0, miny+w/2.0)
        
def test0():
    for x1 in (0,10,20):
        for y1 in (0,10,20):
            for h1 in (10, 50, 100):
                for w1 in (10, 20, 30):
                    R1 = Rect(x1, y1, h1, w1)
                    #pr "rect", R1
                    #pr "  self overlap", R1.overlap(R1)
                    #pr "  self distance", R1.distance(R1)
                    for x2 in (5, 15, 25):
                        for y2 in (5, 15, 25):
                            for h2 in (10, 20, 50):
                                for w2 in (5, 15, 25):
                                    R2 = Rect(x2, y2, h2, w2)
                                    #pr "   other", R2
                                    #pr "   ", R1, "overlap", R2, R1.overlap(R2)
                                    #pr "           distance", R1.distance(R2)
                                    veryClose(R1.overlap(R2), R2.overlap(R1))
                                    veryClose(R2.distance(R1), R1.distance(R2))
                                    assert (R2.distance(R1)>0.0 or R1.overlap(R2,1)>0.00001)
                                    if R1.overlap(R2)>0:
                                        assert R2.distance(R1)==0
                                    if R2.distance(R1)>0.0:
                                        assert R1.overlap(R2)==0
def veryClose(x,y):
    assert abs(x-y)<0.0001

def testLayout():
    idToRectangle = {}
    adjacentPairs = []
    # black in the center
    idToRectangle["black"] = Rect(0,0,25,25, (0,0,0))
    firstid = None
    lastid = "black"
    # ring around black
    for h in range(10, 100, 40):
        for w in range(10, 100, 40):
            label = "h%sw%s" % (h,w)
            R = idToRectangle[label] = Rect(h*2,-w+h,h,w, (h*2, w*2, 255-h-w))
            for i in range(4):
                labi = label+repr(i)
                idToRectangle[labi] = Rect(h,w,10,10, (0,h,w))
                adjacentPairs.append((labi, label))
            #R = idToRectangle[label] = Rect(0,0,15,15, (h*2, w*2, 255-h-w))
            adjacentPairs.append((label, lastid))
            adjacentPairs.append((label, "black"))
            if firstid is None:
                firstid = label
            lastid = label
            print label, R
    adjacentPairs.append( (lastid, firstid) )
    #adjacentPairs = []
    test = layoutRectangles(idToRectangle, adjacentPairs, initOffset=500, debug=True, reduction=0.6, repulsionFactor=10000)
    testitems = test.items()
    testitems.sort()
    adjacentPairs.sort()
    print adjacentPairs
    for x in testitems:
        print x

def testIteration():
    import sys
    #stout = sys.stdout
    htmlout = open("/tmp/R.html", "w")
    #sys.stdout = htmlout
    #RL = [ Rect(-20,0,20,10, (255,0,0)), Rect(100,-20,10,30,(0,255,0)),Rect(-100,0,15,15,(0,0,255)), Rect(30,30,30,30,(0,0,0)),
    #       Rect(10, 10, 8,30, (255,155,0)), Rect(10,10,40,8, (0,255,155))]
    RL = []
    for h in range(10,100,20):
        for w in range(10,100,20):
            R = Rect(h*2,-w+h,h,w, (h*2, w*2, 255-h-w))
            RL.append(R)
    bordersize = 10
    offsets = range(5,100,5)
    offsets.reverse()
    offset = 200
    while offset>10:
        #pr "<pre>"
        for i in xrange(len(RL)):
            R = RL[i]
            newR = R.shift(offset, RL, RL, bordersize=bordersize, repulsionFactor=1.1)
            RL[i] = newR
            #pr RL
        #pr "</pre>"
        from skimpyGimpy import canvas
        c = canvas.Canvas()
        fn = "/tmp/Rects%s.png" % offset
        for R in RL:
            c.setColor(*R.info)
            c.addRect(R.xmin, R.ymin, R.height, R.width)
        c.dumpToPNG(fn)
        htmlout.write("<br>\n<h1>%s</h1>\n" % fn)
        for R in RL:
            htmlout.write("<br>%s\n" % R)
        htmlout.write("""\n<br><img src="%s">\n""" % fn)
        print "wrote", fn
        offset = int(offset*3/4)
    print "wrote /tmp/R.html"
    #sys.stdout = stout

if __name__=="__main__":
    #test0()
    #testIteration()
    testLayout()
